
class GraphError(Exception):
    pass

class Edge(object):
    
    graph = None
    source = None
    target = None
    _dir = None
    _op = None  #opposite edge, only if _dir is False
    
    def __repr__(self):
        if self._dir == self.graph._dir:
            return repr((self.source._id, self.target._id))
        else:          
            return repr((self.source._id, self.target._id, dict([('dir', self._dir)])))
    
    def __init__(self, graph, s, t, dir=None):
        if graph.isvertex(s) and graph.isvertex(t):
            s = graph[s]
            t = graph[t]     
                            
            self.graph = graph
            self.source = s
            self.target = t
            
            graph._edges[self] = (s, t)
            graph._vertices[s].append(t)

            if t in s._neighbors:           # if edge (s,t) already exists
                e = s._neighbors[t]         # get it
                if isinstance(e, list):
                    e.append(self)          # if edges was at least 2, append new
                else:
                    s._neighbors[t] = [e, self]  # or create list with old and new edges
            else:
                s._neighbors[t] = self
            
            if dir is None:                 # if dir isn't setted, use graph defaults
                self._dir = graph.directed
            else:
                self._dir = dir
                
            if not self._dir:                  # if edge is undirected,
                self._op = Edge(graph, t, s, True) # then create opposite one
                self._op._dir = False
                self._op._op = self
        else:
            raise GraphError("Graph contains no at least one of the vertices")
    
    def __getitem__(self, key):
        G = self.graph
        if G.isvertex(key):
            v = G[key]
            if self.source == v: return self.target
            if self.target == v: return self.source
            raise GraphError("Edge %s hasn't end-vertex %s")
        elif G.isedge(key):
            e = G[key]
            if self.source == e.source: return self.source
            if self.source == e.target: return self.source
            if self.target == e.source: return self.target
            if self.target == e.target: return self.target
            raise GraphError("Edges %s and %s haven't cross-vertex", str(self), str(e))
        else:
            raise GraphError("Element %s doesn't exist", str(key))
        
class Vertex(object):
    
    graph = None
    _id = None
    _neighbors = None  # maps neighbor vertex to edge
    
    def __repr__(self):
        return repr([v._id for v in self._neighbors])
    
    #~ def __str__(self):
        #~ return str(self._id)
    
    def __init__(self, graph, id):
        if graph.issupported_id(id):
            if id in graph._ids:
                raise GraphError("Duplicate vertex %s", str(id))
            else:
                graph._vertices[self] = []
                graph._ids[id] = self
                self.graph = graph
                self._id = id
                self._neighbors = {}
        #else:
            #pass #TODO copy vertex
        
    def __getitem__(self, key):
        G = self.graph   
        if G.isvertex(key): 
            if key in self._neighbors:
                return self._neighbors[key]     # v[u] returns edge (v,u)
            raise GraphError("Edge (%s, %s) doesn't exist", str(self), str(key))
        if G.isedge(key):       
            return key[self]                # v[e] returns opposite vertex of edge e relative to v                    
        raise GraphError("Vertex or edge %s doesn't exist", str(key))
    
    def __setitem__(self, key, item):
        #G = self.graph
        #if G.isset(key):
        #    if G.isvertex(key):
        pass
                

class Digraph(Graph):
    def __init__(self, init=None):
      Graph.__init__(self, init)
      self.directed = True      

class Multigraph(Graph):
    def __init__(self, init=None):
      Graph.__init__(self, init)
      self.multigraph = True

class Pseudograph(Graph):
    def __init__(self, init=None):
      Graph.__init__(self, init)
      self.multigraph = True
      self.loops = True
        
class Graph(object):
    
    _vertices = None # maps Vertex to list of neighbors
    _edges = None # maps Edge to tuple of form (source, target) vertices
    _ids = None #maps id to Vertex
    
    __directed = None
    __multigraph = None
    __loops = None    
    
    def __init__(self, init=None):        
        
        if init is None:
            self._vertices = {}
            self._edges = {}
            self._ids = {}
            self._directed = False
            self._multigraph = False
            self._loops = False        
    
    def __repr__(self):
        return repr(dict([(v._id, [u._id for u in v._neighbors]) for v in self._vertices]))        
    
    #~ def __str__(self):
        #~ return "aaaa"

    def setmultigraph(self, value):
        if not value and self.__multigraph:
            if 
        

    def __setattr__(self, name, value):
        if name == multigraph and not value and self.multigraph:
            if self.has_multi_edges():
                raise GraphError('Graph contains multiple edges, call reduce_multi_edges() method before changing it to normal graph')
        if name == loops and not value and self.lopps:
            if self.hasloops():
                raise GraphError('Graph contains loops, call reduceloops() method before changing it to normal graph')
        object.__setattr__(self, name, value)                

    def reduceloops(self):
        pass

    def reduce_multi_edges(self):
        pass

    def hasloops(self):
        pass

    def has_multi_edges(self):
        pass    
    
    def issupported_id(self, id):
        return isinstance(id, int) or isinstance(id, float) or \
                isinstance(id, complex) or isinstance(id, str)
    
    def isset(self, obj):
        return self.isvertex(obj) or self.isedge(obj)
    
    def isvertex(self, obj):
        if isinstance(obj, Vertex):
            return obj in self._vertices
        else:
            return obj in self._ids
        
    def isedge(self, obj1, obj2=None):
        if obj2 == None:
            if isinstance(obj1, Edge):
                return obj1 in self._edges
            elif isinstance(obj1, tuple):
                if len(obj1) == 2:
                    s, t = obj1
                    return self.isedge(s, t)
            return False
        elif self.isvertex(obj1) and self.isvertex(obj2):
            obj1 = self[obj1]
            obj2 = self[obj2]
            return obj2 in self._vertices[obj1]
        return False
        
    def __getitem__(self, key):
        if key in self._edges:
            return key
        elif key in self._vertices:
            return key
        elif isinstance(key, tuple):
            if len(key) == 2:
                s, t = key
                return self[s][t]            
        else:
            try:
                return self._ids[key]
            except KeyError:
                raise GraphError("The graph contains no %s", str(key))
        raise GraphError("The graph contains no %s", str(key))  
        
    def __settitem__(self, key, item):
        pass
    
    def keys(self):
        return self._vertices.keys()
        
    def vertex(self, id):
        return Vertex(self, id)
            
    def edge(self, u, v, dir=None):
        return Edge(self, u, v, dir)

    def V(self):
        return self._id.keys()

    def E(self):
        return self._edges.values() # returns list of tuples (s,t)        
    
